\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

\begin{lstlisting}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 5e5 + 10;
struct Segment_tree
{
	ll l , r;
	ll sum , lmax , rmax , ans;
} tree[N << 2];
ll a[N];
void push_up(ll rt)
{
	tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
	tree[rt].lmax = max(tree[rt << 1].lmax , tree[rt << 1].sum + tree[rt << 1 | 1].lmax);
	tree[rt].rmax = max(tree[rt << 1 | 1].rmax , tree[rt << 1 | 1].sum + tree[rt << 1].rmax);
	tree[rt].ans = max(tree[rt << 1].rmax + tree[rt << 1 | 1].lmax , max(tree[rt << 1].ans , tree[rt << 1 | 1].ans));
}
void build(ll l , ll r , ll rt , ll *aa)
{
	tree[rt].l = l;
	tree[rt].r = r;
	if(tree[rt].l == tree[rt].r)
	{
		tree[rt].sum = a[l];
		tree[rt].lmax = a[l];
		tree[rt].rmax = a[l];
		tree[rt].ans = a[l];
		return ;
	}
	ll mid = l + r >> 1;
	build(l , mid , rt << 1 , aa);
	build(mid + 1 , r , rt << 1 | 1 , aa);
	push_up(rt);
}
void update(ll pos , ll val , ll rt)
{
	if(tree[rt].l == tree[rt].r)
	{
		tree[rt].ans = tree[rt].sum = tree[rt].lmax = tree[rt].rmax = val;
		return ;
	}
	ll mid = tree[rt].l + tree[rt].r >> 1;
	if(pos <= mid)
		update(pos , val , rt << 1);
	if(pos > mid)
		update(pos , val , rt << 1 | 1);
	push_up(rt);
}
Segment_tree query_ans(ll l , ll r , ll rt)
{
	if(l <= tree[rt].l && r >= tree[rt].r)
		return tree[rt];
	ll mid = tree[rt].l + tree[rt].r >> 1;
	if(r <= mid)
		return query_ans(l , r , rt << 1);
	else if(l > mid)
		return query_ans(l , r , rt << 1 | 1);
	else
	{
		Segment_tree Ans , a , b;
		a = query_ans(l , mid , rt << 1);
		b = query_ans(mid + 1 , r , rt << 1 | 1);
		Ans.sum = a.sum + b.sum;
		Ans.lmax = max(a.lmax , a.sum + b.lmax);
		Ans.rmax = max(b.rmax , a.rmax + b.sum);
		Ans.ans = max(a.rmax + b.lmax , max(a.ans , b.ans));
		return Ans;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	int n , m;
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++)
		cin >> a[i];
	build(1 , n , 1 , a);
	while(m --)
	{
		ll x;
		cin >> x;
		if(x == 1)
		{
			ll l , r;
			cin >> l >> r;
			if(l > r)
			swap(l , r);
			cout << query_ans(l , r , 1).ans << '\n';  
		}
		else 
		{
			ll pos , val;
			cin >> pos >> val;
			update(pos , val , 1);
		}
	}
	return 0;
}
\end{lstlisting}

\end{document}
